We prove that () holds pointwise. Take and define .
Then the left-hand side of () equals .
Let denote the set of all those indices such that , hence contains exactly indices.
Given with elements, then belongs to the intersection if and only if is a subset of .
By the combinatorial interpretation of the binomial coefficient, there are $\backslash textstyle\backslash binom\; nk$ such subsets (the binomial coefficient is zero for ).
Therefore the right-hand side of () evaluated at equals
:$\backslash sum\_^m\; \backslash binom\; nk\backslash sum\_^k\; (-1)^\backslash binom\; klc\_l$
=\sum_^m\underbrace\binom nk \binom kl}_ c_l,
where we used that the first binomial coefficient is zero for .
Note that the sum (
*) is empty and therefore defined as zero for .
Using the factorial formula for the binomial coefficients, it follows that
:$$
\begin
(
*)
&=\sum_^n (-1)^\frac\,\frac\\
&=\underbrace}_\underbrace\frac}_\\
\end

Rewriting (
*
*) with the summation index und using the binomial formula for the third equality shows that
:$$
\begin
(
*
*)
&=\sum_^ (-1)^\frac\\
&=\sum_^ (-1)^\binom
=(1-1)^
=\delta_,
\end

which is the Kronecker delta. Substituting this result into the above formula and noting that choose equals for , it follows that the right-hand side of () evaluated at also reduces to .